#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int data;   //结构体中的一个成员
    struct node *next;  //结构体指针，和本结构体类型一样的结构体指针

}linklist_t;    // linklist_t 等价于 struct node

//这个函数功能是在内存中申请了一块结构体大小的内存
//并把申请后的地址返回
linklist_t * create_empty_linklist_head(void)   //创建链表的表头
{
    //malloc(sizeof(linklist_t))  在堆区申请一个结构体大小的内存 16字节
    //(linklist_t*)malloc(sizeof(linklist_t))  把malloc返回的地址强转成结构体指针类型的
    //做完后，就可以用一个结构体指针变量保存这个地址，指针运算时，要求类型必须一致
    //*h  就是一个结构体了
    linklist_t * h = (linklist_t*)malloc(sizeof(linklist_t));
    h->data = 0;    //等价 (*h).data = 0; 
    h->next = NULL;
    return h;   //在堆区申请的内存，生存期是静态生存期，内存不会释放，用户不使用free释放，操作系统不会去释放
}   

//h 是一个结构体指针，保存结构体的地址
//value 要写入的值
int linklist_insert(linklist_t *h,int value)    /*增*/
{
    linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t));   //申请一段内存
    p->data = value;

    p->next = h->next;  //(1)
    h->next = p;    //(2)
    return 0;
}

//遍历内存内容的函数
int linklist_show(linklist_t * h)
{
    linklist_t * p = h->next;
    printf("链表的内容为: ");

    while(p !=NULL)
    {
        printf("%d ",p->data);  //访问节点的内容 3 2 1
        p = p->next;    //节点p 往后移动
    }
    printf("\n");

    return 0;
}

//正常删除链中的一个节点，需要把删除链的前一个节点和后一个节点连接
//需要找到要删除节点的前一个节点才可以删除
int linklist_deleta(linklist_t *h,int value)    /*删*/
{
    //链表中第一个元素的前一个节点就是表头
    linklist_t *p = h;  //p指向要删除节点的前一个节点
    linklist_t *q;
    //第一次执行时，p->next 指向链表的第一个节点 10
    while(p->next != NULL)
    {
        if (p->next->data == value) //value=3 条件成立，找到要删除节点的前一个节点
        {
            //需要一个新的变量保存要删除的节点 使用q
            q = p->next;  //p->next 是要删除的节点，q去保存要删除的节点
            //连接链接
            p->next = q->next;  //链表的前一个和后一个节点连接

            free(q);  //释放申请的内存
            //释放完内存节点后，要立即退出循环或者是返回
            break;
        }
        p = p->next;  //移动
    }
    return 0;
}

int linklist_modify(linklist_t *h,int old,int new)  /*改*/
{
    linklist_t *p = h->next;  //p指向要更改节点的前一个节点

    while(p != NULL)
    {
        if (p->data == old)
        {         
            p->data = new;
            return 0;
        }
        p = p->next;
    }
}

// 找到返回真 1
// 没找到返回假 0 
int linklist_search(linklist_t *h,int value)    /*查*/
{
    linklist_t *p = h->next; // p指向头节点的下一个节点
    while (p != NULL)
    {
        if (p->data == value) // 找到了
        {
            return 1; // 返回为真
        }
        p = p->next; // 移动节点
    }
    return 0; // 没有找到 返回假
    
}

//指针p 指向第一个节点，然后把头设计成空，然后把p 节点插入头的后面，以此类推
//即可实现链表的逆序
int linklist_reverse(linklist_t *h) /*逆序*/
{
    linklist_t * p = h->next;  // p指向第一个节点
    linklist_t * q;
    h->next = NULL;  //把表头置位空头
    while(p != NULL)  // p 指向的链表的节点，不为空表示还有节点
    {
        //把p节点插入到h节点的后面，需要一个q节点保存p的下一个节点
        q = p->next;    //q保存p的下一个节点
        p->next = h->next;  //插入节点 第一步
        h->next = p;  //插入节点 第二步
        p = q;  //让p和q同时指向q
    }
    return 0;
}



int main(int argc, char const *argv[])
{
    //H 保存申请内存的起始地址
    linklist_t * H = create_empty_linklist_head();

    /*
    linklist_insert(H,1);
    linklist_insert(H,2);
    linklist_insert(H,2);
    */
    //使用for循环代替上面代码
    for (int i = 0; i < 10; i++)
    {
        linklist_insert(H,i+1);
    }


    linklist_show(H);   //遍历申请的内存中的内容
    
    /*删除*/
    linklist_deleta(H,5);
    linklist_deleta(H,10);
    linklist_deleta(H,1);
    linklist_show(H);  
    
    /*修改*/
    linklist_modify(H,9,99);
    linklist_modify(H,4,44);
    linklist_modify(H,2,22);
    linklist_show(H);  

    /*查找*/
    if (linklist_search(H, 99))
    {
        printf("99 found\n");
    }
    else
    {
        printf("99 not found\n");
    }
    if (linklist_search(H, 10))
    {
        printf("10 found\n");
    }
    else
    {
        printf("10 not found\n");
    }

    /*倒序*/
    linklist_reverse(H);
    linklist_show(H);
    linklist_reverse(H);
    linklist_show(H);

    return 0;
}
